/*
 *
 * A星算法类  优化
 *   由一个运算为20毫秒的demo做测试
 * 1. 优化获取是否处于open列表和close列表，由原来的indexof判断 修改为设置为节点属性获取，性能提高一倍. 原来20毫秒左右可以降低为10毫秒左右
 * 2. 使用二叉堆来优化open列表的排序性能，运算时间由原来的10毫秒降低为了3毫秒左右
 * */
import { GridData } from "./GridData.js";
import { MinPriorityQueue } from "./MinBinaryHeap";
import { Node, NodeType } from "./Node";

export class AStar {
    gridData: GridData;
    /** 当前算法算出的最短路径 */
    path: Node[] = [];
    /** 已经估价过的节点列表 */
    openList: Node[] = [];
    /** 作为代价最小节点评估过周围八个顶点 */
    closeList: Node[] = [];
    /** 直线代价值 */
    straightCost: number = 1;
    /** 斜线的代价值 */
    diagCost: number = Math.sqrt(2);

    /** 设置当前算法使用到的计算当前节点到终点的估价函数 */
    heuristic: (node: Node) => number;

    /** 二叉堆优化 */
    minBinaryHeap: any;

    startNode: Node;

    endNode: Node;

    constructor(gridData: GridData) {
        this.gridData = gridData;

        this.heuristic = this.manhattan;
    }

    //传入gridData，获取当前路径
    findPath() {
        //重置化一些配置
        this.openList = []; //已经估价过的节点列表
        this.closeList = []; // 作为代价最小节点评估过周围八个顶点
        this.startNode = this.gridData.startNode;
        this.endNode = this.gridData.endNode;

        //使用二叉堆优化open列表
        this.minBinaryHeap = new MinPriorityQueue("f", this.openList);
    }

    //
    search() {
        //首先设置初始节点的代价
        this.startNode.g = 0;
        this.startNode.h = this.heuristic(this.startNode);
        this.startNode.f = this.startNode.g + this.startNode.h;

        //从起点开始遍历，获取到最短路径
        let node = this.startNode;
        while (node !== this.endNode) {
            const startX = Math.max(0, node.x - 1);
            const startY = Math.max(0, node.y - 1);
            const endX = Math.min(this.gridData.cols - 1, node.x + 1);
            const endY = Math.min(this.gridData.rows - 1, node.y + 1);

            for (let i = startX; i <= endX; i++) {
                for (let j = startY; j <= endY; j++) {
                    const searchNode = this.gridData.getNode(i, j);
                    if (searchNode === node || !searchNode.walkable || /*this.isOpen(searchNode) ||*/ this.isClose(searchNode)) continue;
                    //计算当前节点的代价
                    let cost = this.straightCost;
                    if (searchNode.x !== node.x && searchNode.y !== node.y) {
                        cost = this.diagCost;
                    }

                    const g = node.g + cost;
                    const h = this.heuristic(searchNode);
                    const f = g + h;

                    //有些算法是需要额外判断open列表，来查看是否需要更新
                    if (this.isOpen(searchNode)) {
                        //如果此节点处于open列表中，则对当前值和原有值进行判断，是否需要更新
                        if (searchNode.g > g) {
                            //if (searchNode.f > f) {
                            searchNode.g = g;
                            searchNode.h = h;
                            searchNode.f = f;
                            searchNode.parent = node;
                            this.minBinaryHeap.minBinaryHeap.buildHeap(this.openList);
                        }
                    } else {
                        searchNode.g = g;
                        searchNode.h = h;
                        searchNode.f = f;
                        searchNode.parent = node;
                        searchNode.status = NodeType.OPEN;
                        this.minBinaryHeap.insert(searchNode);
                    }
                }
            }

            node.status = NodeType.CLOSE;
            this.closeList.push(node);

            //如果openList内的列表已经为空，则直接退出
            if (this.openList.length === 0) {
                console.warn("无法找到路径！！！");
                // alert("无法找到路径");
                return false;
            }

            node = this.minBinaryHeap.removeMin();
        }

        //构建路径
        this.buildPath();

        return true;
    }

    //构建路径
    buildPath() {
        //从终点向它的父元素去寻找最短路径
        const path = [];
        let node = this.endNode;
        path.push(node);
        while (node !== this.startNode) {
            node = node.parent;
            path.unshift(node);
        }

        this.path = path;
    }

    //获取到当前生成的路径
    getPath() {
        return this.path;
    }

    //获取到此次寻路被访问的节点
    getVisited() {
        return this.openList.concat(this.closeList);
    }

    //判断是否是已经估价过的节点
    isOpen(node: Node) {
        return node.status === NodeType.OPEN;
    }

    //判断是否已经作为小代价评估过周围八个顶点
    isClose(node: Node) {
        return node.status === NodeType.CLOSE;
    }

    //勾股定理 获取当前节点到结束位置的距离
    gouGu(node: Node) {
        const dx = node.x - this.endNode.x;
        const dy = node.y - this.endNode.y;

        return Math.sqrt(dx * dx + dy * dy);
    }

    //曼哈顿估价当前点到终点
    manhattan(node: Node) {
        const dx = node.x - this.endNode.x;
        const dy = node.y - this.endNode.y;
        return Math.abs(dx) * this.straightCost + Math.abs(dy) * this.straightCost;
    }

    //对角线估价函数
    diagonal(node: Node) {
        const dx = Math.abs(node.x - this.endNode.x);
        const dy = Math.abs(node.y - this.endNode.y);
        const diag = Math.min(dx, dy);
        return diag * this.diagCost + this.straightCost * Math.abs(dx - dy); //本人的写法
        //return diag*this.diagCost + this.straightCost * (dx+dy - 2*diag);  //教程的写法
    }
}
